package leetcode;

/**
 * @Project : algorithm-learning-java
 * @Package : leetcode
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/1/18 11:20
 */
public class Q0918 {
    public int maxSubarraySumCircular(int[] nums) {
        int tmp = 0;
        int res = -0x3f3f3f3f;

        for (int i = 0; i < nums.length; i++) {
            tmp = Math.max(tmp, 0) + nums[i];
            res = Math.max(res, tmp);
        }

        int[] leftsum = new int[nums.length + 1];
        int[] rightsum = new int[nums.length + 1];

        for (int i = 0; i < nums.length; i++) {
            leftsum[i + 1] = leftsum[i] + nums[i];
        }

        for (int i = nums.length - 1; i >= 0; i--) {
            rightsum[i] = rightsum[i + 1] + nums[i];
        }

        int leftMax = -0x3f3f3f3f;
        for (int i = 1; i < nums.length; i++) {
            leftMax = Math.max(leftMax, leftsum[i]);
            res = Math.max(res, leftMax + rightsum[i]);
        }

        return res;
    }

    public static void main(String[] args) {
        Q0918 sl = new Q0918();
        int[] nums1 = {1, -2, 3, -2}; // 输出：3
        int[] nums2 = {5, -3, 5}; // 输出：10
        int[] nums3 = {3, -2, 2, -3}; // 输出：3
        int[] nums4 = {-3, -2, -3}; // 输出：3
//        System.out.println(sl.maxSubarraySumCircular(nums1));
//        System.out.println(sl.maxSubarraySumCircular(nums2));
//        System.out.println(sl.maxSubarraySumCircular(nums3));
        System.out.println(sl.maxSubarraySumCircular(nums4));
    }
}
